//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
// Related Topics 字符串 回溯算法
// 👍 1718 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> resList = new ArrayList<>();
//        backtracking(0, 0, n, new StringBuilder(), resList);
        backtarcking2(0, 0, new StringBuilder(), resList);
        return resList;
    }

    public void backtracking(int left, int right, int n, StringBuilder part, List<String> resList) {
        if (left + right == 2 * n) {
            resList.add(part.toString());
            return;
        }
        if (left < n) {
            part.append("(");
            backtracking(left + 1, right, n, part, resList);
            part.deleteCharAt(part.length() - 1);
        }
        if (right < left) {
            part.append(")");
            backtracking(left, right + 1, n, part, resList);
            part.deleteCharAt(part.length() - 1);
        }
    }

    public void backtarcking2(int left, int right, StringBuilder part, List<String> resList) {
        if (left == 0 && right == 0) {
            resList.add(part.toString());
            return;
        }
        if (left == right) {
            backtarcking2(left - 1, right, part.append("("), resList);
        } else if (left < right) {
            if (left > 0) {
                backtarcking2(left - 1, right, part.append("("), resList);
            }
            backtarcking2(left, right - 1, part.append(")"), resList);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
